/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<string> ans;
    bool check(const string &s)
    {
        int l = 0, r = 1;
        while (r < s.size())
        {
            r = s.find_first_of('.', r);
            if (r == s.npos)
                r = s.size();
            string tmp = s.substr(l, r - l);
            if (tmp.length() > 1 && tmp[0] == '0')
                return false; //不能有前导0
            if (tmp.length() > 4)
                return false;
            int i = stoi(s.substr(l, r - l));
            if (!(i >= 0 && i <= 255))
            {
                return false;
            }
            l = r + 1;
            r++;
        }
        return true;
    }

    void dfs(string s, int pos, int count, int start)
    {
        if (count == 3)
        {
            if (check(s))
                ans.push_back(s);
            return;
        }
        if (pos >= s.size())
            return; //不能把点插入到最后一个位置
        if (pos - start > 3)
            return; //两个点之间的最大距离是3

        dfs(s, pos + 1, count, start); //不插入点

        s.insert(s.begin() + pos, '.');
        dfs(s, pos + 2, count + 1, pos + 1); //加2是因为两个点不能相邻
        return;
    }
    vector<string> restoreIpAddresses(string s)
    {
        for (int i = 0; i < s.length(); i++)
        {
            if (!(s[i] >= '0' && s[i] <= '9'))
                return {}; //必须要保证所有的字符都是数字
        }
        dfs(s, 1, 0, 0);
        return ans;
    }
};

// int main()
// {
//     string s("25525511135");
//     Solution().restoreIpAddresses(s);
//     return 0;
// }

// @lc code=end
